package blue_bridge_cup_learning.差分;

import java.util.Arrays;

public class 二维差分 {
    public static void main(String[] args) {
        int[][] arr = {
                { 0, 0, 0, 0 },
                { 0, 1, 2, 3 },
                { 0, 4, 5, 6 },
                { 0, 7, 8, 9 } };
        System.out.println("原数组:");
        打印数组(arr);

        // 构建差分数组
        int[][] diff = 获取差分数组(arr);
        System.out.println("差分数组:");
        打印数组(diff);

        // 区间操作示例: 将子矩阵(1,1)到(2,2)的元素都加2
        区间增加(diff, 1, 1, 2, 2, 2);

        // 通过前缀和还原数组
        int[][] res = 获取前缀和(diff);
        System.out.println("操作后的数组:");
        打印数组(res);
    }

    // 打印二维数组
    public static void 打印数组(int[][] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j < arr[0].length; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
    }

    // 构建差分数组
    public static int[][] 获取差分数组(int[][] arr) {
        int n = arr.length, m = arr[0].length;
        int[][] diff = new int[n + 1][m + 1];

        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                // 当前格子的差分值
                diff[i][j] = arr[i][j] - arr[i - 1][j] - arr[i][j - 1] + arr[i - 1][j - 1];
            }
        }
        return diff;
    }

    // 对子矩阵进行增加操作
    public static void 区间增加(int[][] diff, int x1, int y1, int x2, int y2, int val) {
        diff[x1][y1] += val;
        diff[x2 + 1][y1] -= val;
        diff[x1][y2 + 1] -= val;
        diff[x2 + 1][y2 + 1] += val;
    }

    // 通过差分数组求前缀和得到原数组
    public static int[][] 获取前缀和(int[][] diff) {
        int n = diff.length, m = diff[0].length;
        int[][] sum = new int[n][m];

        for (int i = 1; i < n - 1; i++) {
            for (int j = 1; j < m - 1; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + diff[i][j];
            }
        }
        return sum;
    }
}
